package personal.leil.learning.topo;

import personal.leil.learning.digraph.GraphBuilder;
import personal.leil.learning.digraph.Graph;
import personal.leil.learning.digraph.Node;

import java.util.*;

/**
 * 拓扑排序算法
 * <p>
 * <i>要求：有向无环图</i>
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024/1/23
 */
public class TopologicalSort {

    public static void process(Graph graph) {
        ArrayList<Node> sorted = new ArrayList<>();
        // 查找入度为0的节点
        Queue<Node> queue = new LinkedList<>();
        for (Node node : graph.nodes.values()) {
            if (node.in == 0) {
                queue.offer(node);
            }
        }
        while (queue.size() != 0) {
            Node poll = queue.poll();
            sorted.add(poll);
            for (Node next : poll.nextNodes) {
                next.in--;
                if (next.in == 0) {
                    queue.offer(next);
                }
            }
        }
        // print
        for (Node node : sorted) {
            System.out.println("Node[" + node.value + "]");
        }
    }


    /******************* For Test ********************/
    public static void main(String[] args) {
        Integer[][] matrix = new Integer[][]{
                {1, 2, 0},
                {1, 3, 0},
                {2, 3, 0},
                {2, 4, 0},
                {4, 5, 0},
                {1, 5, 0},
                {6, 4, 0}
        };
        Graph graph = GraphBuilder.build(matrix);
        process(graph);
    }

}
